// #define quickread
#ifdef quickread
#include <cstdio> 
template <typename T>
inline void read(T& x)
{
    int c=getchar(), f=1; x=0;
    while(c<'0'||'9'<c) {if(c=='-') f=-1; c=getchar();}
    while('0'<=c&&c<='9') 
        x=(x<<3)+(x<<1)+c-'0', c=getchar();
    x*=f;
}
template <typename T>
inline void quickwrite(T x)
{
    if(x<0) putchar('-'), x*=-1;
    if(x>=10) quickwrite(x/10);
    putchar(x%10+'0');
}
#else 
#include <iostream>
#endif
#include <vector>
using namespace std;
#define DEBUG

/*
    1.小 小 根据mid判断
        小大小 左区间 否则右区间
    2.小 大 根据mid判断
    3.大 小 
        小则左 否则右
    4.大 大 无解
*/
class Solution {
public:
    int search(vector<int>& nums, int tar) {
        int n=nums.size();
        if(!n) return -1;
        if(n==1) return nums[0]==tar?0:-1;
        int l=0, r=n-1;
        int mid=(l+r)>>1;
        while(l<=r)
        {
            mid=(l+r)>>1;
            // printf("l:%d r:%d mid:%d\n", l, r, mid);
            if(nums[mid]==tar) return mid;
            if(nums[0]<=nums[mid]) //左有序
            {
                if(nums[0]<=tar&&tar<nums[mid]) r=mid-1;
                else l=mid+1;
            }
            else //右有序
            {
                if(nums[mid]<tar&&tar<=nums[n-1]) l=mid+1;
                else r=mid-1;
            }
        }
        return -1;
    }
};

Solution solu;

void solve()
{
    vector<int> a={8,1,2,3,4,5,6,7};
    int target=6;
    cout << solu.search(a, target) << endl;
}

// #undef DEBUG
signed main()
{
    #ifdef DEBUG
        freopen("./in.txt", "r", stdin);
        // freopen("./out.txt", "w", stdout);
    #endif
    #ifndef quickread
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #endif

    int T=1; //scanf("%d", &T);
    while(T--) 
    {
        solve();
    }
    return 0;
}
